// 字符串(主串/单模式串)匹配

/* 四、KMP算法。比BM算法效率差点。模式串从前往后匹配，一次移动多位
   好前缀：遇到相同的前缀，就找这个子串后缀“能对应上模式串的最长前缀“（hash数组缓存所有前缀组合位置）
    1)找到则对齐主串的后缀和子串的前缀
    ababceofg 好前缀abab
    ababf     最长前缀ab
    ->ababf
    2)找不到则移动"好前缀长度"位数
    abcdceofg 好前缀abab
    abcdf     无最长前缀
      ->abcdf

   模式串next数组缓存：
   ababf
   索引 好前缀子串 最长前缀索引
   0   a        -1
   1   ab       -1
   2   aba       0
   3   abab      1
   4   ababf    -1

*/

#include <string.h>

#include <iostream>
using std::cout;
using std::endl;

const char* KnuthMorrisPratt(const char* text, const char* pattern) {
  // next数组缓存
  int patternLen = strlen(pattern);
  int* next = new int[patternLen];

  // 笨方法吧（效率高的看不懂）
  for (int i = 0; i < patternLen; ++i) {
    bool find = false;
    for (int len = i; len > 0; --len) {
      // 借助strncmp清晰很多，如果不让用库函数就自己实现一下
      if (strncmp(pattern, pattern + (i - len + 1), len) == 0) {
        next[i] = len - 1;
        find = true;
        break;
      }
    }
    if (!find) {
      next[i] = -1;
    }
  }
  // print for test
  for (int i = 0; i < patternLen; ++i) {
    cout << next[i] << ' ';
  }
  cout << endl;

  int textLen = strlen(text);
  for (int i = 0; i <= textLen - patternLen; ++i) {
    int j = 0;
    while (j < patternLen && text[i + j] == pattern[j]) {
      j++;
    }
    if (j == 0) {
      continue;
    } else if (j == patternLen) {
      return text + i;
    } else {
      int move = j - next[j - 1] - 1;
      i += move;
    }
  }
}

void TestKMP() {
  const char* p = KnuthMorrisPratt("edababefdababacdxxdefd", "ababacd");
  if (p != NULL) {
    cout << p << endl;
  }
}

int main() {
  TestKMP();
  return 0;
}